package interview.huawei.tjt.training.huisu;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
 */
// 回溯法求解
public class BagOf01 {

    private static List<Integer> result = new ArrayList<>();

    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagSize = 4;
        helper(weight,value,bagSize,0,0,0);
        Collections.sort(result);
        System.out.println(result);
        System.out.println(result.get(result.size() - 1));
    }

    private static void helper (int[] weight, int[] value, int bagSize, int startIndex, int sumWeight, int sumValue) {
        if (sumWeight <= bagSize) {
            result.add(sumValue);
        }

        for (int i = startIndex; i < weight.length; i ++) {
            if (sumWeight > bagSize) break;
            helper(weight,value,bagSize,i + 1, sumWeight + weight[i], sumValue + value[i]);
        }
    }

}
